package com.ifreeee.structure.mutablearray;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * 可变数组 由 链表 链 数组 实现；
 * 相比ArrayList特点是
 *     1）扩容快（add元素的时候 内部数组容量不够 则需要扩容）
 *     2）get元素慢
 */
public class MutableArray {

    //对外
    private int length = 0;//可变数组长度，用户添加了多少个数？
    //对内结构，方便对该结构操作
    private int maxInt = Integer.MAX_VALUE;
    private MutableArrayNode head;//头节点
    private MutableArrayNode end = null;//尾结点，方便扩容
    private int capacity = 10;//该数组当前总容量
    private int expansionLength = 10;//当前尾结点数组长度

    //构造方法，初始容量为10
    public MutableArray()
    {
        head = new MutableArrayNode();
        end = new MutableArrayNode(new int[expansionLength]);
        head.setNext(end);
    }

    /**
     * 返回数组长度
     * @return
     */
    public int size(){
        return this.length;
    }

    /**
     * 内部扩容
     * @return 扩容成功返回true，反之false
     */
    public boolean expansion()
    {
        if(capacity == maxInt)//容量最大，无法扩容
            return false;
        expansionLength = expansionLength > (maxInt - capacity) / 2
                ? (maxInt - capacity)
                : expansionLength * 2;//expansionLength乘以2，但不能超过 maxInt - capacity
        MutableArrayNode n = new MutableArrayNode(new int[expansionLength]);//扩容空间
        end.setNext(n);//设置尾结点的下一个
        end = n;//重新指定尾结点
        capacity += expansionLength;//调整总容量
        return true;
    }

    /**
     * 添加元素到数组的末尾
     * @param num
     * @return
     */
    public boolean add(int num)
    {
        if(length == capacity && !expansion())//容量不够用？扩容直到够用或者 超过Integer.MAX_VALUE返回false！
            return false;
        //够用？然后添加数据进入数组
        Coordinate c = getCoordinate(length);
        c.getNode().getData()[c.getIndex()] = num;
        length += 1;
        return true;
    }

    /**
     * 根据下标获取元素
     * @param index 下标
     * @return 元素
     */
    public int get(int index)
    {
        Coordinate c = getCoordinate(index);
        return c.getNode().getData()[c.getIndex()];
    }

    /**
     * 根据下标 获取 元素详细的位置信息
     * @param index
     * @return
     */
    public Coordinate getCoordinate(int index)
    {
        if(index < 0){
            throw new RuntimeException("下标越界" + index);//下标越界抛出异常
        }
        //找到节点
        MutableArrayNode temp = head.getNext();
        while(temp.getData().length <= index){
            index -= temp.getData().length;
            temp = temp.getNext();
            if(temp == null)
                throw new RuntimeException("下标越界"+ index);//下标越界抛出异常
        }
        return new Coordinate(temp, index);//返回元素详细的位置信息
    }

    /**
     * 可变数组测试（MutableArray 与 ArrayList 对比）
     */
    @Test
    public void test1(){
        Random r = new Random();//随机数对象
        int num1 = 0;//MutableArray的时间
        int num2 = 0;//ArrayList的时间
        int len = 11000000;//测试的数据量
        int time = 20;
        for(int j = 0;j < time;j += 1){
            MutableArray mutableArray = new MutableArray();
            List<Integer> arrayList = new ArrayList<Integer>();
            long t1 = System.currentTimeMillis();
            for(int i = 0;i<len;i+=1){
                int n = r.nextInt(50000);
                mutableArray.add(n);
            }
            for(int i = 0;i<len;i+=1){
                int n = mutableArray.get(i);
            }

            long t2 = System.currentTimeMillis();

            for(int i = 0;i<len;i+=1){
                int n = r.nextInt(50000);
                arrayList.add(n);
            }
            for(int i = 0;i<len;i+=1){
                int n = arrayList.get(i);
            }
            long t3 = System.currentTimeMillis();
            num1 += (t2 - t1);
            num2 += (t3 - t2);
        }

        System.out.println("数据量：" + len + "\n测试次数：" + time);
        System.out.println("MutableArray耗时：" + num1 + "\nArrayList耗时：" + num2);
        /*
            数据量：10000000
            测试次数：20
            MutableArray耗时：17741
            ArrayList耗时：17655

            数据量：10000000
            测试次数：20
            MutableArray耗时：17256
            ArrayList耗时：20650

            数据量：9000000
            测试次数：20
            MutableArray耗时：15192
            ArrayList耗时：11845

            结论：不理想，只有在数据量大的情况下才有优势
            改进：
                1）双策略扩容（低于500万的数据量则使用 copyOf 的方式扩容，超过500万则用 链表 链接一个 新的数组）；
                2）双参数add的功能也要添加进去（从中间插入）
                3）remove 和 removeAll 的功能也要添加进去
                4）indexOf和lastIndexOf
                5）isEmpty
        */
    }

}




